//////////////////////////////////////////////////
// EASIM project
// easim.net.DTDV
// 6/18/2007 2:11 PM
// Cong Liu
// gzcong@gmail.com

// Copyright (C) 2007
// All rights reserved.
// Refer to LICENSE of JIST (Java In Simulation Time) for terms and conditions of use.

package easim.omar;

import easim.net.DtnNodeInterface;
import easim.net.Timer;
import easim.net.Clock;

import jist.swans.Constants;
import jist.swans.misc.Message;
import jist.runtime.JistAPI.DoNotRewrite;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Iterator;

public class DTDV implements DtnNodeInterface, DoNotRewrite
{

  public static long TIME_BREAK_EPSILON = DtnNodeInterface.CONTACT_TIMEOUT / 5;
  public static long TIME_BREAK = DtnNodeInterface.CONTACT_TIMEOUT + TIME_BREAK_EPSILON;
  public static final long INIT_TIME = - 1000 * Constants.SECOND;
  public static final long MESSAGE_INTERVAL3 = TIME_BREAK / 5;
  public static final int MAX_HOP = 5;
    
  /** class TableItem */
  public class TableItem implements Timer, DoNotRewrite
  {
    public int dst = -1;
    public int next = -1;
    public int hop = Integer.MAX_VALUE;
    public long dstTime = INIT_TIME;
    public long updateTime = INIT_TIME;

    public String toString() {
      return dst + " " + next + " " + (hop == Integer.MAX_VALUE ? "-" : "" + hop) + " " + 
        dstTime + " " + updateTime;
    }
    public void copyTo(TableItem item) {
      item.dst = dst;
      item.next = next;
      item.hop = hop;
      item.dstTime = dstTime;
      item.updateTime = updateTime;
    }
    public TableItem getClone() {
      TableItem item = new TableItem();
      copyTo(item);
      return item;
    }
    public void timeout() {
      if (updateItemFromRecord(this)) {
        rateChecker.schedule();
      }
    }
  } // end class TableItem

  /** class ContactInfo */
  protected class ContactInfo implements DoNotRewrite
  {
    public int id;
    public int maxHop;
    public long lastUpdateSentTime = INIT_TIME;
    public long refreshTime = INIT_TIME;
    public HashMap table = new HashMap();
  } // end class ContactInfo

  /** class UpdateMessage */
  public static class UpdateMessage implements Message, DoNotRewrite
  {
    public long time;
    public int maxHop;
    public boolean fullDumpReq;
    public HashMap table;
    public int getSize() {
      return 9 + 20 * table.size();
    }
    public void getBytes(byte[] msg, int offset) {
      throw new RuntimeException("no implementation.");
    }
    // for rollback, not part of the message exactly.
    public HashMap rbInfo;
  } // end class UpdateMessage

  /** class RateChecker1 */
  public class RateChecker1 extends RateChecker implements DoNotRewrite
  {
    public RateChecker1(int events, long bound) {
      super(events, bound);
    }
    public void timeout() {
      sendingPermission = true;
      node.startJitterTimer();
    }
  } // end class RateChecker1

  ///////////////////////////
  // variables
  //

  public HashMap table = new HashMap();
  protected int maxHop = MAX_HOP;
  protected Node node;
  protected HashMap contacts = new HashMap();
  protected long refreshTime = INIT_TIME;
  protected long updateTime = INIT_TIME;
  protected RateChecker1 rateChecker = 
    new RateChecker1(2, DtnNodeInterface.HELLO_INTERVAL_MIN);
  protected boolean sendingPermission = false;

  public DTDV(Node node) {
    this.node = node;
    TableItem item = new TableItem();
    item.dst = node.getId();
    item.dstTime = Clock.getTime();
    item.next = item.dst;
    item.hop = 0;
    table.put(new Integer(item.dst), item);
  }

  public void onContactDetected(int contactId) {
    ContactInfo info = new ContactInfo();
    info.id = contactId;
    contacts.put(new Integer(contactId), info);
    rateChecker.schedule();
  }

  public void onContactBroken(int contactId) {
    long curTime = Clock.getTime();
    if (refreshTime < curTime) {
      refreshTable(table, refreshTime, curTime);
      refreshTime = curTime;
    }
    Iterator it = table.values().iterator();
    LinkedList updated = new LinkedList();
    while (it.hasNext()) {
      TableItem item = (TableItem)it.next();
      if (item.next == contactId) {
        item.next = -1;
        item.hop = Integer.MAX_VALUE;
        item.updateTime = curTime;
        updateTime = curTime;
        updated.addLast(item);
      }
    }
    contacts.remove(new Integer(contactId));
    if (updated.size() > 0) {
      updateTableFromRecord(updated);
      rateChecker.schedule();
    }
  }

  /// must be called from a method that has called 'refreshTable'
  protected boolean updateTableFromRecord(LinkedList items) {
    TableItem[] table = (TableItem[])items.toArray(new TableItem[0]);
    return updateTableFromRecord(table);
  }

  protected boolean updateItemFromRecord(TableItem item) {
    //System.out.println("***************");
    //item = (TableItem)table.get(new Integer(item.dst));
    //if (item == null) return;
    long curTime = Clock.getTime();
    if (refreshTime < curTime) {
      refreshTable(table, refreshTime, curTime);
      refreshTime = curTime;
    }
    return updateTableFromRecord(new TableItem[] {item});
  }

  /// must be called from a method that has called 'refreshTable'
  protected boolean updateTableFromRecord(TableItem[] table) {
    long curTime = Clock.getTime();
    TableItem[][] tables = new TableItem[contacts.size()][];
    int[] contactIds = new int[tables.length];
    Iterator it = contacts.values().iterator();
    for (int j = 0; j < tables.length; ++ j) {
      ContactInfo info = (ContactInfo)it.next();
      contactIds[j] = info.id;
      if (info.refreshTime < curTime) {
        refreshTable(info.table, info.refreshTime, curTime);
        info.refreshTime = curTime;
      }
      tables[j] = new TableItem[table.length];
      for (int i = 0; i < table.length; ++ i) {
        tables[j][i] = (TableItem)info.table.get(new Integer(table[i].dst));
      }
    }
    boolean updated2 = false;
    for (int i = 0; i < table.length; ++ i) {
      boolean updated = true;
      while (updated) {
        updated = false;
        for (int j = 0; j < tables.length; ++ j) {
          if (tables[j][i] == null) continue;
          if (updateItem(table[i], tables[j][i], contactIds[j], curTime)) {
            updateTime = curTime;
            updated = true;
            updated2 = true;
          }
        }
      }
    }
    scheduleUpdates(table, tables);
    return updated2;
  }

  protected void scheduleUpdates(TableItem[] table, TableItem[][] tables) {
    long curTime = Clock.getTime();
    for (int i = 0; i < table.length; ++ i) {
      if (table[i].hop == Integer.MAX_VALUE) {
        long delay = Long.MAX_VALUE;
        for (int j = 0; j < tables.length; ++ j) {
          if (tables[j][i] == null) continue;
          //if (tables[j][i].hop == Integer.MAX_VALUE) continue;
          if (tables[j][i].hop >= maxHop) continue;
          long delay2 = table[i].dstTime - tables[j][i].dstTime + 
            (TIME_BREAK - TIME_BREAK_EPSILON + 1);
          if (delay2 > 0 && delay > delay2) delay = delay2;
        }
        if (delay == Long.MAX_VALUE) {
          if (tables.length == 0) { // if no contact
            this.table.remove(new Integer(table[i].dst));
          }
          else {
            if (table[i].updateTime + TIME_BREAK <= curTime) {
              this.table.remove(new Integer(table[i].dst));
            }
            else {
              delay = table[i].updateTime + TIME_BREAK - curTime;
            }
          }
        }
        if (delay != Long.MAX_VALUE) {
          if (delay > TIME_BREAK) {
            delay = TIME_BREAK;
          }
          Clock.start(table[i], delay, true);
        }
      }
    }
  }

  public void receiveMessage(Message message, int srcId) {
    UpdateMessage uMsg = (UpdateMessage)message;
    long curTime = Clock.getTime();
    ContactInfo info = (ContactInfo)contacts.get(new Integer(srcId));
    info.maxHop = uMsg.maxHop;
    if (maxHop < info.maxHop - 1) {
      setMaxHop(info.maxHop - 1);
    }
    if (uMsg.fullDumpReq) {
      info.lastUpdateSentTime = INIT_TIME;
    }
    if (uMsg.table.size() == 0) return;
    if (info.refreshTime < curTime) {
      refreshTable(info.table, info.refreshTime, curTime);
      info.refreshTime = curTime;
    }
    incrementalUpdate(info.table, uMsg.table, curTime);
    if (refreshTime < curTime) {
      refreshTable(table, refreshTime, curTime);
      refreshTime = curTime;
    }
    LinkedList updated = updateTable(table, uMsg.table, srcId, curTime);
    //cleanTable(info.table, curTime);
    if (updated.size() > 0) {
      updateTime = curTime;
      updateTableFromRecord(updated);
      rateChecker.schedule();
    }
  }

  public Message nextMessageToSend() {
    if (sendingPermission) {
      sendingPermission = false;
    }
    else {
      return null;
    }
    long curTime = Clock.getTime();
    UpdateMessage uMsg = new UpdateMessage();
    uMsg.time = curTime;
    uMsg.maxHop = maxHop;
    uMsg.table = new HashMap();
    long lastUpdateTime = curTime;
    Iterator it = contacts.values().iterator();
    while (it.hasNext()) {
      ContactInfo info = (ContactInfo)it.next();
      if (lastUpdateTime > info.lastUpdateSentTime) {
        lastUpdateTime = info.lastUpdateSentTime;
      }
    }
    if (lastUpdateTime > updateTime) return null;
    if (refreshTime < curTime) {
      refreshTable(table, refreshTime, curTime);
      refreshTime = curTime;
    }
    it = table.values().iterator();
    long latestUpdateTime = lastUpdateTime;
    while (it.hasNext()) {
      TableItem item = (TableItem)it.next();
      if (item.updateTime >= lastUpdateTime) {
        uMsg.table.put(new Integer(item.dst), item.getClone());
        if (latestUpdateTime < item.updateTime) {
          latestUpdateTime = item.updateTime;
        }
      }
    }
    //if (uMsg.table.size() == 0) {
    //  return null;
    //  //throw new RuntimeException("impossible situation (" + node.getId() + ").");
    //}
    uMsg.rbInfo = new HashMap();
    it = contacts.values().iterator();
    while (it.hasNext()) {
      ContactInfo info = (ContactInfo)it.next();
      if (info.lastUpdateSentTime <= latestUpdateTime) {
        uMsg.rbInfo.put(new Integer(info.id), new Long(info.lastUpdateSentTime));
      }
      info.lastUpdateSentTime = curTime;
    }
    //System.out.println(toString(node.getId(), uMsg.table));
    rateChecker.addTime();
    ++ Stats.send.dtdvMsgs;
    Stats.send.dtdvMsgSize += uMsg.getSize();
    return uMsg;
  }

  public void onAckMessage(Message message) {
    UpdateMessage uMsg = (UpdateMessage)message;
    ++ Stats.recv.dtdvMsgs;
    Stats.recv.dtdvMsgSize += uMsg.getSize();
  }

  /** rollback the update information */
  public void onDropMessage(Message message, int[] dstIds) {
    UpdateMessage uMsg = (UpdateMessage)message;
    boolean dropped = false;
    for (int i = 0; i < dstIds.length; ++ i) {
      int unacked = dstIds[i];
      Long lastUpdateSentTime = (Long)uMsg.rbInfo.get(new Integer(unacked));
      if (lastUpdateSentTime == null) continue;
      ContactInfo contact = (ContactInfo)contacts.get(new Integer(unacked));
      if (contact == null) continue;
      contact.lastUpdateSentTime = lastUpdateSentTime.longValue();
      dropped = true;
    }
    if (dropped) {
      rateChecker.schedule();
    }
    else {
      onAckMessage(message);
    }
  }

  /** refresh a given table */
  public static void refreshTable(HashMap table, long refreshTime, long curTime) {
    long dtime = curTime - refreshTime;
    if (dtime == 0) return;
    Iterator it = table.values().iterator();
    while (it.hasNext()) {
      TableItem item = (TableItem)it.next();
      if (item.hop != Integer.MAX_VALUE) {
        item.dstTime += dtime;
      }
    }
  }

  /** clean up infinity metrics */
  public static void cleanTable(HashMap table, long updateTime) {
    Iterator it = table.values().iterator();
    while (it.hasNext()) {
      TableItem item = (TableItem)it.next();
      if (item.hop == Integer.MAX_VALUE && item.updateTime <= updateTime) {
        it.remove();
      }
    }
  }

  /** update item1 with item2 of node id2 */
  public boolean updateItem(TableItem item1, TableItem item2, int id2, long curTime) {
    if (id2 == item1.next) {
      if (item1.hop == Integer.MAX_VALUE && item2.hop == Integer.MAX_VALUE) return false;
      if (item1.hop == item2.hop + 1) return false;
      if (item2.hop == Integer.MAX_VALUE || item1.hop < item2.hop + 1) {
        item1.next = -1;
        item1.hop = Integer.MAX_VALUE;
      }
      else {
        item1.hop = item2.hop + 1;
        item1.dstTime = item2.dstTime - TIME_BREAK;
      }
      item1.updateTime = curTime;
      return true;
    }
    else if (item2.next != -1 && (item1.next == -1 || item1.hop - item2.hop > 1) && 
      item2.dstTime - item1.dstTime > TIME_BREAK - TIME_BREAK_EPSILON && item2.hop < maxHop)
    {
      item1.next = id2;
      item1.hop = item2.hop + 1;
      item1.dstTime = item2.dstTime - TIME_BREAK;
      item1.updateTime = curTime;
      return true;
    }
    return false;
  }

  /** update table1 with table2 of node id2 */
  public LinkedList updateTable(HashMap table1, HashMap table2, int id2, long curTime) {
    Iterator it = table2.values().iterator();
    LinkedList updated = new LinkedList();
    while (it.hasNext()) {
      TableItem item2 = (TableItem)it.next();
      TableItem item1 = (TableItem)table1.get(new Integer(item2.dst));
      if (item1 == null) {
        //if (item2.hop == Integer.MAX_VALUE) continue;
        if (item2.hop >= maxHop) continue;
        item1 = new TableItem();
        item1.dst = item2.dst;
        table1.put(new Integer(item1.dst), item1);
      }
      if (updateItem(item1, item2, id2, curTime)) {
        updated.addLast(item1);
      }
    }
    return updated;
  }

  /** update the mirror table of the neighbor */
  public void incrementalUpdate(HashMap table, HashMap incremental, long curTime) {
    Iterator it = incremental.values().iterator();
    while (it.hasNext()) {
      TableItem item2 = (TableItem)it.next();
      if (item2.next == node.getId() || item2.hop > maxHop) {
        table.remove(new Integer(item2.dst));
      }
      else {
        TableItem item1 = (TableItem)table.get(new Integer(item2.dst));
        if (item1 == null) {
          item1 = item2.getClone();
          table.put(new Integer(item1.dst), item1);
        }
        else {
          item2.copyTo(item1);
        }
        item1.updateTime = curTime;
      }
    }
  }

  public int getMaxHop() {
    return maxHop;
  }

  public void setMaxHop(int hop) {
    if (hop > MAX_HOP) return;
    /**/
    int maxNeighborMaxHop = 0;
    Iterator it = contacts.values().iterator();
    while (it.hasNext()) {
      ContactInfo info = (ContactInfo)it.next();
      if (maxNeighborMaxHop < info.maxHop) {
        maxNeighborMaxHop = info.maxHop;
      }
    }
    if (hop < maxNeighborMaxHop - 1) {
      hop = maxNeighborMaxHop - 1;
    }
    long curTime = Clock.getTime();
    if (maxHop <= hop) {
      if (maxHop != hop) {
        maxHop = hop;
        updateTime = curTime;
      }
    }
    else if (maxHop > 0) {
      -- node.dtdv.maxHop;
      updateTime = curTime;
    }
  }

  public String toString() {
    String buf = "DTDV=\r\n";
    for (int i = 1; i < 1000; ++ i) {
      TableItem item = (TableItem)table.get(new Integer(i));
      if (item == null) continue;
      buf += item.dst + " " + item.next + " " + item.hop + "\r\n";
    }
    return buf;
  }

  public static String toString(int id, HashMap table) {
    String buf = "[" + id + "] DTDV=\r\n";
    for (int i = 1; i < 1000; ++ i) {
      TableItem item = (TableItem)table.get(new Integer(i));
      if (item == null) continue;
      buf += item.dst + " " + item.next + " " + item.hop + "\r\n";
    }
    return buf;
  }

}
